<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 1. Геометрия.2D.advanced</h2>
<ol>
  <li>Метод двух указателей</li>
  <ol>
    <li>Две самые дальние точки на плоскости за O(n)</li>
    <li>Расстояние между выпулкыми непересекающимися многоугольниками за O(n)</li>
    <li>Общая касательная к многоугольникам за O(n)</li>
    <li>Прямая, разделяющая многоугольники за O(n)</li>
    <li>Сумма Минковского за O(n)</li>
    <li>Поиск расстояния между выпуклыми многоугольниками + проверки их пересечения через сумму Минковского.</li>
  </ol></li>
  <li>Выпуклая оболочка</li>
  <ol>
    <li>QuickHull --- алгоритм, работающий в среднем за O(n) и за O(nlogM) в худшем</li>
    <li>Мелкман --- выпуклая оболочка многоугольника за O(n)</li>
  </ol></li>
  <li>Пересечение</li>
  <ol>
    <li>Простое пересечение выпуклых многоугольников за O(n<sup>2</sup>)</li>
    <li>Пересечение выпуклых многоугольников за O(n)</li>
    <li>Пересечение n полуплоскостей за O(nlogn) (сортировка + стэк)</li>
    <li>Задача линейного программирования в 2D за O(n) (нашли одну точку в пересечении полуплоскостей)</li>
    <li>Пересечение и объединение невыпуклых многоугольников за O(n<sup>3</sup>)</li>
    <li>Пересечение и объединение кругов за O(n<sup>3</sup>)</li>
  </ol></li>
  <li>Планарный граф</li>
  <ol>
    <li>Построение планарного графа, задающего пересечение невыпуклых многоугольников</li>
    <li>Пересечение и объединение многоугольников и кругов за O(n<sup>2</sup>logn)</li>
    <li>Разбиение планарного графа на грани за O(n)</li>
    <li>Теорема Эйлера. Задача про количество частей плоскости.</li>
  </ol></li>
  <li>Алгоритм A* (модификация Дейкстры)</li>
  <li>Сортировка по углу</li>
  <ol>
    <li>Нахождение диагоналей невыпуклого многоугольника за O(n<sup>2</sup>logn)</li>
    <li>Задача "провести точку  на плоскости, обходя выпуклые многоугольные препятствия" за O(n<sup>2</sup>logn)</li>
    <li>Задача "провести треугольник" (Лоцман с тимуса). Сумма Минковского.</li>
  </ol></li>
</ol>
